package 力扣日常刷题.木22一月.第03天0110;

import java.util.ArrayList;

/**
 * @author 帅小伙
 * @date 2022/1/10
 * @description
 */
public class Demo04回溯中等无重复字符串的排列组合 {

    char[] chars ;
    boolean[] isUsed;
    int n;
    ArrayList<String> res;
    public String[] permutation(String S) {
        chars = S.toCharArray();
        n = S.length();
        isUsed = new boolean[n];
        res = new ArrayList<>();
        dfs(0,new StringBuffer());
        return res.toArray(new String[res.size()]);
    }

    void  dfs(int index,StringBuffer sb) {
        if(index==n){
            res.add(sb.toString());
            return ;
        }

        for (int i = 0; i < n; i++) {
            if(!isUsed[i]){
                sb.append(chars[i]);
                isUsed[i] = true;
                dfs(index+1,sb);
                isUsed[i] =false;
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}
